import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LXW
 * Date: 2022-01-15
 * Time: 15:36
 */
public class Problem {
    // 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    //
    //push(x) —— 将元素 x 推入栈中。
    //pop()—— 删除栈顶的元素。
    //top()—— 获取栈顶元素。
    //getMin() —— 检索栈中的最小元素。
    //来源：力扣（LeetCode）155题
    //链接：https://leetcode-cn.com/problems/min-stack
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    public void push(int val) {
        stack.push(val);
        if (!minStack.empty()) {
            if (val <= minStack.peek()) {
                minStack.push(val);
            }
        }else {
            minStack.push(val);
        }
    }
    public void pop() {
        int popVal = stack.pop();
        if (!minStack.empty()) {
            if (popVal == minStack.peek()) {
                minStack.pop();
            }
        }
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }

    // 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
    // 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    //1. 0<=pushV.length == popV.length <=1000
    //2. -1000<=pushV[i]<=1000
    //3. pushV 的所有数字均不相同
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack =new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
          while (j < popA.length && !stack.empty() && pushA[i] == popA[j]) {
              stack.pop();
              j++;
          }
        }
        return stack.empty();
    }
    //根据 逆波兰表示法(后缀表达式），求表达式的值。
    //    有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式.
    //    说明：整数除法只保留整数部分。
    //    给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。(力扣150题)
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!isOperation(tokens[i])) {
                stack.push(Integer.parseInt(tokens[i]));
            }
            int num2 = stack.pop();
            int num1 = stack.pop();
            String val = tokens[i];
            switch (val){
                case"+":
                    stack.push(num1+num2) ;
                    break;
                case"-":
                    stack.push(num1-num2);
                    break;
                case"*":
                    stack.push(num1*num2);
                    break;
                case"/":
                    stack.push(num1/num2);
                    break;
            }
        }
        return stack.pop();
    }
        private boolean isOperation(String x) {
        if (x == "+" ||x == "-" ||x == "*" ||x == "/") {
            return true;
        }
        return false;
    }
    //    来源：力扣（LeetCode）
    //    链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
    //    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    // 给定一个只包括 '('，')'，'{'，'}'，'['，']的字符串 s ，判断字符串是否有效。
    //有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合
    //来源：力扣（LeetCode）
    //链接：https://leetcode-cn.com/problems/valid-parentheses
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c =='(' || c == '{' || c == '['){
                stack.push(c);
            }else {
                if (stack.empty()) {
                    System.out.println("右括号多");
                    return false;
                }
                char top = (char)stack.peek();
                if (c == '(' && top == ')' || c == '{' && top == '}' || c == '[' && top == ']') {
                    stack.pop();
                }else {
                    System.out.println("左右括号不匹配");
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            System.out.println("左括号多");
            return false;
        }
        return true;
    }
}
